home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-02 / sortdemo.zip / SDSORT02.INC < prev    next >
Text File  |  1992-04-15  |  3KB  |  70 lines
  1. (*
  2. ╔═══════════════════════════════════════════════════════════════════════════╗
  3. ║ Turbo Pascal 6.0 Include File : SDSORT02.INC                              ║
  4. ╟───────────────────────────────────────────────────────────────────────────╢
  5. ║ Program : SORTDEMO.PAS                                                    ║
  6. ╟───────────────────────────────────────────────────────────────────────────╢
  7. ║ Version : 1.0                                                             ║
  8. ╟───────────────────────────────────────────────────────────────────────────╢
  9. ║ Copyright (c) 1992  by  Jon S. Russell                                    ║
  10. ╟───────────────────────────────────────────────────────────────────────────╢
  11. ║ Short-bubble sort routine for SORTDEMO.PAS                                ║
  12. ╚═══════════════════════════════════════════════════════════════════════════╝
  13.                                                                            *)
  14. procedure ShortBubbleSort (var Info : InfoType);
  15. var
  16.   Current     : IndexType;
  17.   DoneSorting : boolean;
  18.  
  19.   (*───────────────────────────────────────────────────────────────────────*)
  20.  
  21.   procedure BubbleUp (var Info        : InfoType;
  22.                           StartIndex  : IndexType;
  23.                           EndIndex    : IndexType;
  24.                       var DoneSorting : boolean);
  25.   var
  26.     Index : IndexType;
  27.  
  28.   begin  (* BubbleUp *)
  29.     DoneSorting := true;  (* start out optimistic *)
  30.  
  31.     (* Loop Invariant:  StartIndex <= Index <= EndIndex AND *)
  32.     (* List[Index+1] .. List[EndIndex] >= List[Index].      *)
  33.  
  34.     for Index := EndIndex downto StartIndex+1 do
  35.       if (Info.List[Index].Key < Info.List[Index-1].Key) then
  36.         begin
  37.           Swap(Info,Index,Index-1);
  38.           DoneSorting := false;
  39.         end;
  40.   end;   (* BubbleUp *)
  41.  
  42.   (*───────────────────────────────────────────────────────────────────────*)
  43.  
  44. begin  (* ShortBubbleSort *)
  45.   Current := 1;   (* index of first unsorted element *)
  46.   DoneSorting := false;
  47.  
  48.   (* Loop Invariant: 1 <= Current <= Info.Len AND    *)
  49.   (* the values in List[1] .. List[Current-1] are    *)
  50.   (* sorted and are less than or equal to the values *)
  51.   (* in List[Current] .. List[Len].                  *)
  52.  
  53.   while (not DoneSorting) and (Current < Info.Len) do
  54.     begin
  55.  
  56.       (* Bubble up the smallest element from unsorted *)
  57.       (* part of the list, with intermediate swaps.   *)
  58.  
  59.       BubbleUp(Info, Current, Info.Len, DoneSorting);
  60.  
  61.       (* Shrink the unsorted part of the list. *)
  62.  
  63.       Inc(Current);
  64.     end; (* while *)
  65.  
  66.   Info.Sorted := true;  (* set flag *)
  67. end;   (* ShortBubbleSort *)
  68.  
  69. (*─────────────────────────────────────────────────────────────────────────*)
  70.